#include <stdio.h>
#include <assert.h>

typedef struct bt_node* link;

struct bt_node
{
    char item;
    link l;
    link r;
};

int count(link h);
int height(link h);
void printnode(char c, int h);
void show(link x, int h);
void show_pre(link x, int h);

int main(int argc, char** argv){
    struct bt_node root;
    struct bt_node dNode;
    struct bt_node hNode;
    struct bt_node bNode;
    struct bt_node fNode;
    struct bt_node aNode;
    struct bt_node cNode;
    struct bt_node gNode;





    root.item = 'E';
    root.l = &dNode;
    root.r = &hNode;

    dNode.item = 'D';
    dNode.l = &bNode;
    dNode.r = NULL;
    hNode.item = 'H';
    hNode.l = &fNode;
    hNode.r = NULL;

    bNode.item = 'B';
    bNode.l = &aNode;
    bNode.r = &cNode;
    fNode.item = 'F';
    fNode.l = NULL;
    fNode.r = &gNode;

    aNode.item = 'A';
    aNode.l = NULL;
    aNode.r = NULL;
    cNode.item = 'C';
    cNode.l = NULL;
    cNode.r = NULL;
    gNode.item = 'G';
    gNode.l = NULL;
    gNode.r = NULL;

    printf("Testing count function...\n");

    assert(count(NULL) == 0);

    assert(count(&aNode) == 1);
    assert(count(&cNode) == 1);
    assert(count(&gNode) == 1);

    assert(count(&bNode) == 3);
    assert(count(&fNode) == 2);

    assert(count(&dNode) == 4);
    assert(count(&hNode) == 3);

    assert(count(&root) == 8);
    printf("Testing count function passed...\n");

    printf("Testing height function...\n");

    assert(height(NULL) == -1);

    assert(height(&aNode) == 0);
    assert(height(&cNode) == 0);
    assert(height(&gNode) == 0);

    assert(height(&bNode) == 1);
    assert(height(&fNode) == 1);

    assert(height(&dNode) == 2);
    assert(height(&hNode) == 2);

    assert(height(&root) == 3);
    printf("Testing height function passed...\n");

    printf("Testing show function...\n");
    show(&root, 3);
    printf("Testing show function passed...\n");
    printf("Testing show_pre function...\n");
    show_pre(&root, 3);
    printf("Testing show_pre function passed...\n");

    return 0;
}

int count(link h){
    if (h == NULL) {
        return 0;
    }
    return count(h->l) + count(h->r) + 1;
}

int height(link h){
    if (h == NULL) {
        return -1;
    }
    int u = height(h->l);
    int v = height(h->r);
    if (u > v) {
        return u+1;
    }else {
        return v+1;
    }
}


void show(link x, int h){
    if (x == NULL) {
        printnode('*', h);
        return ;
    }
    show(x->r, h+1);
    printnode(x->item, h);
    show(x->l, h+1);
}

void show_pre(link x, int h){
    if (x == NULL) {
        printnode('*', h);
        return ;
    }
    printnode(x->item, h);
    show_pre(x->l, h+1);
    show_pre(x->r, h+1);
}

void printnode(char c, int h){
    int i;

    for (i = 0; i < h; i++) {
        printf("  ");
    }
    printf("%c\n", c);
}
